#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "datrie.h"
#include "charset.h"
#include "mylog.h"

static const unsigned char utf8_mask[] = {0x1F, 0x7F, 0x7F};

#define EN_CHAR(s, i)	((char)(s)[(i)] & utf8_mask[(i)%3])

static int grow(dat * p)
{
	assert(p != NULL);
	assert(sizeof(struct dat_node) >= sizeof(struct tag_node));
	if(p->_base + DAT_SCALE < p->_volume){
		return 1;
	}
	unsigned int new_volume = 
		((p->_base + DAT_SCALE) / DAT_BLOCK_SIZE + 1) * DAT_BLOCK_SIZE;
	dat_node * new_da = 
		(dat_node *)realloc( p->_da, new_volume * sizeof(struct dat_node));
	if(new_da == NULL){
		LOGIT(LV_FATAL, "dat realloc %x", new_volume * sizeof(struct dat_node));
		return -1;
	}
	memset(new_da + p->_volume, 0, 
		(new_volume - p->_volume) * sizeof(struct dat_node));
	p->_da = new_da;
	p->_volume = new_volume;
	LOGIT(LV_DEBUG, "dat realloc [%p]%.1fM", 
		p->_da, (float)(p->_volume * sizeof(struct dat_node)) / (1<<20));
	return 0;
}

dat * dat_new()
{
	LOGIT(LV_LOG, "datrie new ...");
	dat * p = (dat *)malloc(sizeof(struct dat));
	if(p == NULL){
		return NULL;
	}
	memset(p, 0, sizeof(struct dat));
	return p;
}

int _dat_dump_init(dat * p)
{
	assert(p != NULL);
	p->_root = DAT_DEF_ROOT;
	p->_base = DAT_DEF_ROOT + 1;
	p->_dt = (dict_item *)malloc(sizeof(struct dict_item) * DICT_SIZE);
	if(p->_dt == NULL){
		return -1;
	}
	memset(p->_dt, 0, sizeof(struct dict_item) * DICT_SIZE);
	if(grow(p) < 0){
		return -2;
	}
	return 0;
}

int dat_free(dat * p)
{
	assert( p != NULL);
	LOGIT(LV_LOG, "datrie free ...");
	free(p->_da);
	p->_da = NULL;
	p->_volume = 0;
	p->_root = 0;
	p->_base = 0;
	free(p->_dt);
	p->_dt = NULL;
	p->_dt_size = 0;
	free(p);
	return 0;
}

//1. if res == NULL, fetch until depth(depth from 0 to len-1) and return parent 
//2. if res == NULL, fetch until depth(depth == len) and return cur node 
//3. if depth < 0 and res != NULL, fetch all result
int dat_fetch(const dat *p, const char * str, int depth, dat_res * res)
{
	if(p == NULL || str == NULL ){
		return -1;
	}
	int i = 0;
	unsigned char ch = '\0';
	int parent = p->_root;
	int base = p->_root + 1;

	if(depth < 0){
		depth = DICT_WORD_LEN;
	}
	if(res != NULL){
		memset(res, 0, sizeof(struct dat_res));
	}

#define ISASCII(c)    (((c) & ~0x7f) == 0)
	for(i=0; i<depth; i++){
		if(ISASCII(str[i])){	//cant find english
			break;
		}
		ch = EN_CHAR(str, i);//encode utf8 to reduce space
		base = p->_da[parent].base;
		if(p->_da[base+ch].base == 0 && p->_da[base+ch].check == 0){
			if(res == NULL){
				LOGIT(LV_ERROR, "fetch: %s:%d[%x] prefix can't be found", 
					str, i, (unsigned int)ch);
			}
			break;
		}
		if(abs(p->_da[base+ch].check) != parent){
			if(res == NULL){
				LOGIT(LV_ERROR,
					"fetch: %s:%d[%x] clue broken, check:%d, parent:%d",
					 str, i, (unsigned int)ch, p->_da[base+ch].check, parent
				);
			}
			break;
		}
		//is a termination, set res
		if(res != NULL && p->_da[base+ch].check < 0){
			res->item[res->num].len = i+1;
			res->item[res->num].headi = p->_da[base+ch].headi;
			assert(res->item[res->num].len > 0);
			res->num ++;
			if(res->num == DAT_RES_MAX){
				LOGIT(LV_ERROR, "fetch too more res");
				return -2;
			}
		}
		parent = base + ch;
	}
#undef ISASCII
	return parent;
}

static int _dat_insert(dat *p, int j, int depth)
{
	assert(p != NULL && j >= 0 && depth >= 0);
	dict_item *t = &(p->_dt[j]);
	unsigned char ch = t->word[depth];
	if(ch == '\0'){
		LOGIT(LV_ERROR, "insert: %s, %d, mustn't be termination", t->word, depth);
		return -1;
	}
	ch = EN_CHAR(t->word, depth);
	int parent = dat_fetch(p, t->word, depth, NULL);
	if(parent < 0){
		LOGIT(LV_ERROR, "parent too large\n");
		return -2;
	}
	//first node with same prefix
	if(p->_da[parent].base == 0){
		//{parent.base + ch = cur}, set cur just here that cur = p->_base
		//but avoid parent.base == 0, for child.check != 0
		p->_da[parent].base = (p->_base - ch == 0)?1:(p->_base - ch);
	}
	int base = p->_da[parent].base;
	//there is a node
	if(p->_da[base+ch].check != 0){
		//it's not my child
		if(abs(p->_da[base+ch].check) != parent){
			return -3;
		}
		//node has been established
		return 1;
	}
	p->_da[base+ch].base = 0;
	p->_da[base+ch].check = parent;
	//if it's a termination, set freq 
	if(depth + 1 == t->len){
		p->_da[base+ch].check = - parent;
	}
	p->_base = base + ch + 1;
	p->_size ++;
	if(p->_base + DAT_SCALE > p->_volume && grow(p) < 0){
		return -6;
	}
	return 0;
}

//return the offset of tag_node
static int _dat_insert_tag(dat *p, int j){
	dict_item * t = &(p->_dt[j]);
	int cur = dat_fetch(p, t->word, t->len, NULL);
	if(cur < 0){
		LOGIT(LV_ERROR, "insert tag_node: fetch fail");
		return -1;
	}
	dat_node * curp = &p->_da[cur];
	assert(curp->check < 0 && curp->headi == 0);
	//head
	curp->headi = p->_base;
	tag_head * headp = HEADAT(p, curp->headi);
	memset(headp, 0, sizeof(struct tag_head));
	//grow
	p->_base ++;
	if(p->_base + DAT_SCALE > p->_volume && grow(p) < 0){
		return -2;
	}
	int i;
	for(i=DAT_TAG_MAX-1; i>=0; i--){
		if((t->tags+i)->id == 0){
			continue;
		}
		//create tag_node
		tag_node * tagp = (tag_node *)&p->_da[p->_base];
		//set it
		tagp->id = t->tags[i].id;
		tagp->freq = t->tags[i].freq;
		//set to the head of headi list
		int k = TAGK(tagp->id);
		if(k == TAG_POS || k == TAG_GRAM){
			tagp->tagi = headp->grami;
			headp->grami = p->_base;
		}else if(k == TAG_NR || k == TAG_NS || k == TAG_TR){
			tagp->tagi = headp->rolei;
			headp->rolei = p->_base;
		}else if(k == TAG_UNGRAM){
			tagp->tagi = headp->ungrami;
			headp->ungrami = p->_base;
		}else{
			LOGIT(LV_ERROR, "insert tag_node: invalid tagk");
			return -3;
		}
		//grow
		p->_base ++;
		if(p->_base + DAT_SCALE > p->_volume && grow(p) < 0){
			return -4;
		}
		if(i == DAT_TAG_MAX-1){
			LOGIT(LV_ERROR, "insert tag_node: %s may be more tags", t->word);
		}
	}
	return 0;
}

static int check_order(dict_item *p, int size)
{
	assert(p != NULL);
	if(size < 2){
		return 0;
	}
	int i = 0;
	for(i=0; i<size-1; i++){
		if(strncmp((p + i)->word, (p + i+1)->word, DICT_WORD_LEN) > 0){
			LOGIT(LV_ERROR, "wrong order while cmp line %d with %d", i+1, i+2);
			return -1;
		}
	}
	return 0;
}

static int _dat_build(dat *p)
{
	assert(p != NULL && p->_dt != NULL && p->_dt_size >= 0);
	if(p->_dt_size == 0){
		return 1;
	}

	if(check_order(p->_dt, p->_dt_size) < 0){
		fprintf(stderr, "check order failed\n");
		return -1;
	}

	int i = 0;
	int j = 0;
	int flag = 0;
	//each time process one byte
	//make index 1 to be root and base is 2
	for(i=0; i<DICT_WORD_LEN; i++){
		flag = 0;
		for(j=0; j<p->_dt_size; j++){
			if(i >= (p->_dt+j)->len){
				continue;
			}
			if(_dat_insert(p, j, i) < 0){
				return -2;
			}
			flag ++;
		}
		if(flag == 0){
			break;
		}
	}
	//build tags
	for(j=0; j<p->_dt_size; j++){
		if(_dat_insert_tag(p, j) < 0){
			return -3;
		}
	}
	LOGIT(LV_LOG, "build: size/base/volume: %d/%d/%d", p->_size, p->_base, p->_volume);
	return p->_size;
}

static int check_cjk(char *str)
{
	assert(str != NULL);
	int i = 0;
	int len = strlen(str);
	for(i=0; i<len; i++){
		if((str[i] & (~utf8_mask[i%3])) != ~utf8_mask[i%3]){
			return -1;
		}
	}
	return 0;
}

int dat_load(dat * p, const char * dat_path)
{
	if(p == NULL || dat_path == NULL){
		return -1;
	}
	FILE *datfp = fopen(dat_path, "r");
	if(datfp == NULL){
		return -2;
	}
	p->_root = DAT_DEF_ROOT;
	if(fread(&p->_size, sizeof(int), 1, datfp) != 1){
		return -3;
	}
	if(p->_size < 0){
	LOGIT(LV_ERROR, "load size %d", p->_size);
		return -4;
	}
	p->_base = p->_size + 1;
	p->_volume = 0;
	if(grow(p) < 0){
		return -5;
	}
	if(fread(p->_da, sizeof(struct dat_node), p->_size, datfp) != p->_size){
		return -6;
	}
	fclose(datfp);
	return 0;
}
	
int dat_dump(dat * p, const char * dict_path, const char * dat_path)
{
	if(p == NULL || dict_path == NULL || dat_path == NULL){
		return -1;
	}
	FILE *dictfp = fopen(dict_path, "r");
	if(dictfp == NULL){
		return -2;
	}
	FILE *datfp = fopen(dat_path, "w+");
	if(datfp == NULL){
		return -3;
	}
	if(_dat_dump_init(p) < 0){
		return -4;
	}
	dict_item * t = p->_dt;
	int i = 0;
	int ret = 0;
	char * s = NULL;
	char line[DICT_ITEM_LEN] = {0};
	while(fgets(line, DICT_ITEM_LEN, dictfp)){
		if((s=strstr(line, "\n")) == NULL){
			fprintf(stderr, "%s is longer than %u, line %u\n", 
					line, DICT_ITEM_LEN, i);
			continue;
		}
		*s = '\0';
		//DAT_TAG_MAX = 35 
		//FIXME
		assert(DAT_TAG_MAX == 35);
		ret = sscanf(line, "%s "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d "
						"%u %d %u %d %u %d %u %d %u %d ",
			t->word,
			&t->tags[0].id, &t->tags[0].freq, 
			&t->tags[1].id, &t->tags[1].freq, 
			&t->tags[2].id, &t->tags[2].freq, 
			&t->tags[3].id, &t->tags[3].freq, 
			&t->tags[4].id, &t->tags[4].freq, 
			&t->tags[5].id, &t->tags[5].freq, 
			&t->tags[6].id, &t->tags[6].freq, 
			&t->tags[7].id, &t->tags[7].freq,
			&t->tags[8].id, &t->tags[8].freq,
			&t->tags[9].id, &t->tags[9].freq,
			&t->tags[10].id, &t->tags[10].freq,
			&t->tags[11].id, &t->tags[11].freq,
			&t->tags[12].id, &t->tags[12].freq,
			&t->tags[13].id, &t->tags[13].freq,
			&t->tags[14].id, &t->tags[14].freq,
			&t->tags[15].id, &t->tags[15].freq,
			&t->tags[16].id, &t->tags[16].freq,
			&t->tags[17].id, &t->tags[17].freq,
			&t->tags[18].id, &t->tags[18].freq,
			&t->tags[19].id, &t->tags[19].freq,
			&t->tags[20].id, &t->tags[20].freq,
			&t->tags[21].id, &t->tags[21].freq,
			&t->tags[22].id, &t->tags[22].freq,
			&t->tags[23].id, &t->tags[23].freq,
			&t->tags[24].id, &t->tags[24].freq,
			&t->tags[25].id, &t->tags[25].freq,
			&t->tags[26].id, &t->tags[26].freq,
			&t->tags[27].id, &t->tags[27].freq,
			&t->tags[28].id, &t->tags[28].freq,
			&t->tags[29].id, &t->tags[29].freq,
			&t->tags[30].id, &t->tags[30].freq,
			&t->tags[31].id, &t->tags[31].freq,
			&t->tags[32].id, &t->tags[32].freq,
			&t->tags[33].id, &t->tags[33].freq,
			&t->tags[34].id, &t->tags[34].freq
		);
		if(strlen(t->word) > DICT_WORD_LEN - 1){
			fprintf(stderr, "%s is longer than %u\n", t->word, DICT_WORD_LEN);
			return -5;
		}
		if(check_cjk(t->word) < 0){
			fprintf(stderr, "%s is not cjk\n", t->word);
			memset(t, 0, sizeof(struct dict_item));
			continue;
		}
		if(++ i == DICT_SIZE){
			fprintf(stderr, "words is more than %u\n", DICT_SIZE);
			return -6;
		}
		t->len = strlen(t->word);
		t ++;
	}
	p->_dt_size = i;
	if(_dat_build(p) < 0){
		return -7;
	}
	if(fwrite(&p->_base, sizeof(int), 1, datfp) < 0){
		return -8;
	}
	if(fwrite(p->_da, sizeof(struct dat_node), p->_base, datfp) < 0){
		return -9;
	}

	fclose(dictfp);
	fclose(datfp);
	return 0;
}

#ifdef DATRIE_MAIN
int main(int argc, char ** argv)
{
	LOGON("stdout");
	dat * p = dat_new();
	int ret = dat_dump(p, "/home/aaron/workspace/hiseg/clasdict/hidict.dct", "/home/aaron/workspace/hiseg/clasdict/hidict.dat");
	if(ret < 0){
		printf("dump err, %d\n", ret);
		return 1;
	}
	dat_free(p);
	p = dat_new();
	ret = dat_load(p, "/home/aaron/workspace/hiseg/clasdict/hidict.dat");
	if(ret < 0){
		printf("load dict, ret=%d\n", ret);
		return 1;
	}

	dat_res res;
	ret = dat_fetch(p, "和平", -1, &res);
	if(ret < 0){
		printf("fetch, ret=%d\n", ret);
		return 2;
	}
	printf("res: %d\n", res.num);
	int i = 0;
	for(i = 0; i<res.num; i++){
		printf("%d: %d, %d\n", i, res.item[i].len, res.item[i].headi);
		tag_head * headp = HEADAT(p, res.item[i].headi);
		int tagi;
		tagi = headp->grami;
		while(tagi){
			tag_node * tagp = TAGAT(p, tagi);
			printf("\t%u %u %d\n", tagp->id, tagp->freq, tagp->tagi);
			tagi = tagp->tagi;
		}
		printf("----------------\n");
		tagi = headp->rolei;
		while(tagi){
			tag_node * tagp = TAGAT(p, tagi);
			printf("\t%u %u %d\n", tagp->id, tagp->freq, tagp->tagi);
			tagi = tagp->tagi;
		}
		printf("----------------\n");
		tagi = headp->ungrami;
		while(tagi){
			tag_node * tagp = TAGAT(p, tagi);
			printf("\t%u %u %d\n", tagp->id, tagp->freq, tagp->tagi);
			tagi = tagp->tagi;
		}
	}

	dat_free(p);
	LOGOFF();
	return 0;
}
#endif
